A triangle is a polygon with three vertices, three edges, and three angles (between each pair of edges). One important property that is true for any triangle is that the three angles always sum up to $180^\circ$.
Write a method/function below called isValidTriangle that takes in three arguments, ang_1, ang_2, and ang_3 (all positive), and prints "YES" if they can be the angles of a triangle, and prints "NO" if they cannot.
For example isValidTriangle(90, 45, 45) would print "YES", isValidTriangle(10, 10, 160) would print "YES", but isValidTriangle(90, 90, 90) would print "NO".
Just a reminder, the syntax for creating a function is
def isValidTriangle(arg_1, arg_2, arg_3):
#Implement your code here
In [3]:
#Write your code here
#Solution
def isValidTriangle(arg_1, arg_2, arg_3):
if(arg_1 + arg_2 + arg_3 == 180):
print "YES"
else:
print "NO"
We can categorize triangles into three categories based on the properties of their angles.
For example if a triangle had the angles of $15^\circ, 85^\circ, 80^\circ$, it would be acute.
For example if a triangle had the angles of $15^\circ, 15^\circ, 150^\circ$, it would be obtuse.
The pythagorean theorem deals with (and only applies) to right triangles. If we notice from the picture above, the right angle is opposite to the longest side, we call this the hypotenuse. We call the other two shorter sides the legs. We denote the legs with $A$, and $B$, and the hypotenuse with $C$, shown in the picture below.
The pythagorean statements simply states that $A^2 + B^2 = C^2$. Although this equation may look really simple, it is quite powerful. Conversly, if a triangle has three sides $A, B, C$ such that $A^2 + B^2 = C^2$, then it must be a right triangle.
The theorem is quite useful because if we know any the length of any two sides of a right triangle, we can figure out the length of the third.
For example, if we know the lengths of both the legs of a right triangle are $3$ and $4$, then the pythagorean theorem tells us that $3^2 + 4^2 = C^2 \rightarrow C = \sqrt{3^2+4^2} = \sqrt{9+16} = \sqrt{25} = 5$.
If we know the length of the hypotenuse and the length of one leg, we can figure out the length of the remaining leg. For example, if we know that a right triangle has a hypotenuse with length 13, and a leg of length 12, then the pythagorean theorem tells us that $A^2 + 12^2 = 13^2 \rightarrow A^2 = 13^2-12^2 \rightarrow A = \sqrt{13^2-12^2} = \sqrt{169-144} = \sqrt{25} = 5$.
Now we will write some methods that deal with the pythagorean theorem.
Write a method that, when given the length of the legs of a right triangle, return the length of the hypotenuse. Call it find_hypotenuse.
Write another method that, when given the length of the length of a single leg and the hypotenuse, return the length of the other leg. Notice that the order that the order of the inputs may not be in order of (leg, hypotenuse), so you will have to figure out a way to over come this! Call it find_leg
You may find it useful to first call
import math
You can use its squareroot method by calling
math.sqrt(x)
In [4]:
#Write your functions here
import math
#Solutions
def find_hypotenuse(a, b):
return math.sqrt(a*a+b*b)
def find_leg(a,b):
if(a > b):
return math.sqrt(a*a-b*b)
else:
return math.sqrt(b*b-a*a)
The pythagorean theorem lets us easily find the distance between any two cartesian points. This is because if we visualize two points on a cartesian grid, the distance between them is just the length of the hypotenuse created by connecting the two points! See the figure below:
Since this is a right triangle, we know that $distance(P_1, P_2)^2 = |x_2-x_1|^2 + |y_2-y_1|^2 \rightarrow distance(P_1, P_2) = \sqrt{|x_2-x_1|^2 + |y_2-y_1|^2}$
Write a function below called distance that takes in four arguments, x1, y1, x2, y2, corresponding to the points $p_1 = (x_1, y_1)$ and $p_2 = (x_2, y_2)$ and returns the distance between $p_1$ and $p_2$.
In [5]:
#Write your function here
#Solution
def distance(x1,y1,x2,y2):
return math.sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1))
Now that we can find the distance between cartesian points, we can now find the TDOA of four sensors on a plane instead of the TDOA along just a single line with two sensors!
When we set up the sensors, they will be on the four corners of a rectangle with width $a$ and height $b$. Thus the positions of the sensors are at $(0,0)$, $(a,0)$, $(b,0)$, and $(a,b)$. Whenever we tap within this rectangular region, we will be creating a circular wave with a velocity $v$, that travels to the four corners. Since we don't know exactly where we tapped, have it be at a variable point $(x,y)$.
Write a function that takes in four arguments, $a$ (width of the rectangle), $b$ (height of the triangle), and $x,y$, the cartesian coordinates of the wave source and return an array/list of length four, where the first element is the distance from the wave source to the first sensor, the second element is the distance from the wave source to the second sensor, etc. Call it distance_to_sensor.
Hint: you may find it useful to use the distance function you defined above.
In [7]:
#Write your function below
#Solution
def distance_to_sensor(a,b,x,y):
distance_one = distance(0,0,x,y)
distance_two = distance(a,0,x,y)
distance_three = distance(0,b,x,y)
distance_four = distance(a,b,x,y)
return [distance_one, distance_two, distance_three, distance_four]
Now write a function that takes in the four parameters above, but an additional one called $v$ which is the velocity of the wave source. Have this function return an array/list of length four with the time it takes for the wave to reach of the sensors. Call it time_to_sensor.
In [44]:
#Write your function below
#Soluton
def time_to_sensor(a,b,x,y,v):
distances = distance_to_sensor(a,b,x,y)
time_one = distances[0]/v;
time_two = distances[1]/v;
time_three = distances[2]/v;
time_four = distances[3]/v;
#return map(lambda x: x/v, distances)
return [time_one, time_two, time_three, time_four]
Now we will write a method that returns the "Time distance of arrival" relative to sensor one. This means that we shift our position in time such the time it takes to reach sensor one is zero. We can do this by subtracting the time it takes to get to sensor one from every single element in the return value from the time_to_sensor method.
Wrte a method that takes in the same parameters as time_to_sensor, but returns the TDOA, where each "time" is relative to sensor one.
Call it TDOA.
In [9]:
#Write your function below
#Soluton
def TDOA(a,b,x,y,v):
times = time_to_sensor(a,b,x,y,v)
offset = times[0];
return map(lambda x: x-offset, times)
Now we have successfully written a method that can return the theoretical TDOA to our sensors of a wave source! However, what we would ideally like is a way that can identify what the position $(x,y)$ is given the time distance of arrivals. The implementation for this is rather difficut, so we will not go into it. However, it is the same method that is used by seismologists to detect an earthquake, and what a GPS might use to determine your location!
Some things to think about though. If we know which sensor has the least TDOA is (remember, some of them can be negative since we are subtracting the time it takes the wave to get to sensor one. If the time difference is negative, it simply means that the wave reached that sensor before it reached sensor one), we can figure out which quadrant (or identify an area) that the wave source must be from. Discuss how we can do this.
We've written an implementation that takes in the TDOA. You can import this and use it to create a 2D touch screen!
In this section we will talk about a simple way of determining where the source of a disturbance is given the values of the TDOA.
For simplicity, imagine that we place the sensors on a square of sidelength $a$. One way we could hypothetically find the location is to test every single possible point within the square, and look for the point that returns the correct TDOA values. However, this is unfeasible because there are an infinite number of points within the grid, and it would be impossible to check every single point. But, instead of looking at every single point, we can look a finite number of points and look for the one whose TDOA values are the closest to that of the ones we are given.
In the picture above, we are dividing each side into 8 points, and checking a total of $8^2 = 64$ points for the one with the best TDOA values. However, to make it more accurate, we can easily divide each side into $100$ points, and check a total of $10000$ points, which a computer can easily handle. If we are given a two TDOA arrays, we can define an error function, which is how "different" the two arrays are. We want to find the point in the grid that returns a TDOA array that is the most similar to the actual TDOA.
Implement a function that, given the length of the board, a TDOA array and the velocity of a wave in the material, returns the coordinate of a point, whose cost is the least. Call it find_point. Use a subdivision along each side of 101 points.
The heading should look like
def find_point(a, time_differences, v):
#your code here
Hint: It may be useful to use two loops to scan through the possible points and it may be useful to use several variables to keep track of the minimum and the corresponding coordinates as we are scanning through every single possible point.
In [10]:
#definition of cost function
def err(TDOA1, TDOA2):
ans = 0
for i in range(1,4):
ans += (TDOA1[i] - TDOA2[i])*(TDOA1[i] - TDOA2[i])
return ans
In [17]:
#Write your method below
#Solution
def find_point(a, time_differences, v):
currentX = -1
currentY = -1
min_error = 100000000
x = 0.0
while(x <= a):
y = 0.0
while(y <= a):
error = err(time_differences, TDOA(a,a,x,y,v))
if(error < min_error):
min_error = error
currentX = x
currentY = y
y = y+a/100.0
x = x+a/100.0
return (currentX,currentY)
In [45]:
print find_point(1, [0, 0, .618033, .618033], 1)
print TDOA(1,1, .5, 0, 1)
In [ ]: